package com.xzz.finger;

import java.util.LinkedList;
import java.util.List;

/**
 * @author: hhz
 * @create: 2022-02-24 14:17
 * 剑指 Offer 34. 二叉树中和为某一值的路径
 **/
public class PathSum {
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(5);
        TreeNode node2 = new TreeNode(4);
        TreeNode node3 = new TreeNode(8);
        TreeNode node4 = new TreeNode(11);
        TreeNode node5 = new TreeNode(13);
        TreeNode node6 = new TreeNode(4);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(2);
        TreeNode node9 = new TreeNode(1);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node3.left = node5;
        node3.left = node6;
        node4.left = node7;
        node4.right = node8;
        node5.right = node9;

        System.out.println(pathSum(node1, 22));
    }
    static LinkedList<List<Integer>> res ;
    public static List<List<Integer>> pathSum(TreeNode root, int target) {
        res = new LinkedList<>();
        traverse(root,target,new LinkedList<>());
        return res;
    }
    public static void traverse(TreeNode root,int target,LinkedList<Integer> list) {
        if(root==null){
            return;
        }
        int rest = target-root.val;
        if(root.left==null && root.right==null){
            if(rest==0){
                list.addLast(root.val);
                res.add(new LinkedList<>(list));
                list.removeLast();
            }
            return;
        }

        list.addLast(root.val);
        traverse(root.left,rest,list);
        list.removeLast();

        list.addLast(root.val);
        traverse(root.right,rest,list);
        list.removeLast();
    }
}
